package KMP;

public class demo1 {
    public static void main(String[] args) {
        String s1 = "ababcddffffk";
        String s2 = "abc";
        kmp(s1,s2);
    }
    public static int kmp(String str,String sub){
        if (str == null || sub == null){
            return -1;
        }
        if (str.length() == 0 || sub.length() == 0){
            return -1;
        }
        int strLen = str.length();
        int subLen = sub.length();
        int[] next = new int[subLen];
        getNext(sub,next);
        int i = 0;
        int j = 0;
        while (i < strLen && j < subLen){
            if ( j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if (j>=subLen){
            System.out.println("找到了 :" + (i-j) + " 到 " + (i-1));
            return i-j;
        }
        System.out.println("没找到");
        return -1;
    }

    public static void getNext(String sub,int[] next){
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        int len = sub.length();
        while (i < len){
            if ( k == -1 || sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k+1;
                k++;
                i++;
            }else {
                k = next[k];
            }
        }
    }
}
